Pada tahun 826, Euphemius, komander armada Byzantine di Sicily, telah memaksa seorang biarawati untuk mengahwini beliau. Maharaja Michael II menghidu khabar angin ini dan mengarahkan Jeneral Constantine untuk menghentikan perkahwinan ini dan memotong hidung Euphemius. Euphemius menentang, membunuh Constantine dan kemudian menawan Syracuse. Beliau kemudian dikalahkan dan melarikan diri ke Afrika Utara.[1] Beliau menawarkan pemerintahan Sicily kepada Ziyadat Allah Emir Tunisia dari dinasti Aghlabid sebagai balasan untuk tempat tinggal dan keselamatan; satu pasukan tentera Arab kemudian dihantar untuk memberi bantuan.[1]

Pihak Arab kemudian bersetuju untuk menakluk Sicily, berjanji akan menyerahkannya kepada Euphemius sebagai pertukaran untuk ufti tahunan, dan memberi kepercayaan kempen penaklukan ini kepada seorang kadi yang berumur 70 tahun, Asad ibn al-Furat. Pasukan Muslim seramai 10,000 infantri, 700 kavalri dan 100 kapal, dan diperkuat dengan kapal-kapal daripada Euphemius, berjaya mendarat di Mazara del Vallo. Pertempuran pertama menentang tentera yang setia kepada Byzantine berlaku pada 15 Julai, 827, berdekatan Mazara, menghasilkan kemenangan kepada Aghlabid.

Asad kemudian menawan pantai di bahagian selatan pulau serta mengepung Siracusa. Selepas setahun dikepung, dan cubaan dahagi, tentera beliau berjaya mengalahkan satu pasukan besar tentera yang dihantar dari Palermo, dengan bantuan daripada armada Venice yang diketuai oleh Doge Giustiniano Participazio. Tetapi apabila wabak membunuh ramai tentera Muslim, termasuk Asad sendiri, Muslim berundur ke istana kota Mineo. Mereka kemudian membuat serangan tetapi gagal menawan Castrogiovanni (kini Enna, di mana Euphemius meninggal dunia) dan berundur kembali ke Mazara.

Pada tahun 830, mereka menerima tentera tambahan seramai 30,000 daripada Ifriqiya dan Andalusia. Muslim Iberia berjaya mengalahkan komander Byzantine, Teodotus pada bulan Julai–Ogos pada tahun itu, tetapi wabak sekali memaksa mereka kembali ke Mazara dan kemudian ke Ifriqiya. Unit-unit Ifriqiya dihantar untuk mengepung Palermo dan berjaya menawannya pada bulan September 831 setelah setahun dikepung.[8] Palermo menjadi ibu kota Muslim di Sicily, dinamakan semula sebagai al-Madinah ("Kota").[9]

Penaklukan ini melihat hubungan pasang-surut; dengan tentangan dan pergolakkan dalaman, ia mengambil masa lebih sekurun untuk Sicily Byzantine ditakluk sepenuhnya. Syracuse berjaya memberi tentangan buat beberapa ketika tetapi berjaya ditawan pada tahun 878, Taormina jatuh pada tahun 902, dan kota Byzantine terakhir berjaya ditawan pada tahun 965.[1]